package com.sali.数据结构;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 */
public class LeetCode_316 {

    public String removeDuplicateLetters(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();

        // 记录每个字符最后一次出现的索引
        int[] lastOccurrence = new int[26];
        for (int i = 0; i < n; i++) {
            lastOccurrence[chars[i] - 'a'] = i;
        }

        Deque<Character> stack = new ArrayDeque<>(); // 用双端队列模拟栈
        boolean[] inStack = new boolean[26]; // 记录字符是否已在栈中

        for (int i = 0; i < n; i++) {
            char current = chars[i];
            int idx = current - 'a';

            // 如果当前字符已在栈中，跳过
            if (inStack[idx]) {
                continue;
            }

            // 栈不为空时，检查栈顶元素是否需要弹出
            while (!stack.isEmpty() &&
                    stack.peek() > current &&
                    lastOccurrence[stack.peek() - 'a'] > i) {
                // 栈顶字符比当前字符大，且后续还会出现，弹出栈顶
                char top = stack.pop();
                inStack[top - 'a'] = false;
            }

            // 将当前字符压入栈，并标记为已存在
            stack.push(current);
            inStack[idx] = true;
        }

        // 将栈中的字符转为字符串（注意顺序，栈顶是最后添加的）
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pollLast()); // 从栈底到栈顶顺序输出
        }
        return result.toString();
    }

}
